package 笔试2.pdd.two;

import java.util.HashSet;
import java.util.Set;

//迷宫
/*
3
3 3 7
1 1 2
5 5 8
3 9 7

3 3 6
10 9 6
10 10 10
1 7 4

3 3 7
1 4 9
10 6 10
3 3 5
 */
//左上到右下无重复颜色 迷宫
public class Main2 {

    static Set<Integer> set = new HashSet<>();

    static int res=0;
    /*只改这里———————————————————————————————————————————————————*/
    static void qian(int i, int j) {
        ptIntShuzu(g);
        for (int k=0;k<fx.length;k++) {
            int x=i+fx[k][0],y=j+fx[k][1];

            //停止
            if(x<0||x>=g.length||y<0||y>=g[0].length //越界
                    || g[x][y]==-1  //vis走过
                    || set.contains(g[x][y]) // 有重复颜色
            ) continue;

            //终点
            if(x==g.length-1 && y==g[0].length-1){
                System.out.println("+++++");
                res++;
                continue; //多种情况
            }

            //other全都能走 (con排-1 6 return排2 -> 就剩’0‘)
            step++; int t=g[x][y]; g[x][y]=-1; set.add(t);
            qian(x,y);
            step--; g[x][y]=t;                   set.remove(t);

        }
    }
    /*—————————————————————————————————————————————————————————*/

    static int[][] g = {
            //1起点 -1障碍 6走过 2终点 0可走
            //停止:-1 6
            //return: 2
            //可走 (0)
//            {1,1,2},
//            {5,5,8},
//            {3,9,7},

//            {10,9,6},
//            {10,10,10},
//            {3,9,7}
            {1,4,9},
            {10,6,10},
            {3,3,5},
    };
    static int[][] fx = {{1,0},{0,1}};
    public static void main(String[] args) {
        set.add(g[0][0]);
        g[0][0]=-1;
        qian(0,0);

        System.out.println("共几种路径"+res);
    }
    static int step=0;
    static int resMin=9999;
    static void ptIntShuzu(int[][] p){
        for (int i = 0; i < p.length; i++) {
            for (int j = 0; j < p[0].length; j++) {
                System.out.print(String.format("%3s",p[i][j] + " " ));
            }
            System.out.println();
        }
        System.out.println("——————————————————————————");
    }
}
